package org.alg.graph;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class DepthFirstPaths {
	private boolean[] marked;
	private int[] edgeTo; //从起点到一个顶点的已知路径的最后一个顶点
	private final int s; //起点
	
	public DepthFirstPaths(Graph G,int s){
		marked=new boolean[G.V()];
		edgeTo=new int[G.V()];
		this.s=s;
		dfs(G,s);
	}
	
	private void dfs(Graph G,int v){
		marked[v]=true;
        Iterable<Integer> adjs=G.adj(v);
		for(int w:adjs){
			if(!marked[w]){
				edgeTo[w]=v;
				dfs(G,w);
			}
				
		}
	}

    public boolean hasPathTo(int v){
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v){
        if(!hasPathTo(v))return null;

        List<Integer> path=new ArrayList<Integer>();
        for(int x=v;x!=s;x=edgeTo[x]){
            path.add(x);
        }

        path.add(s);
        return path;
    }

    public void printEdgeToS(){
        for(int i=0;i<edgeTo.length;i++){
            System.out.println(i+":"+edgeTo[i]);
        }
    }

    public void printPathToV(int v){
        Iterable<Integer> path=pathTo(v);
        Iterator<Integer> it=path.iterator();
        if(path==null||it==null||!it.hasNext()) {
            System.out.println("from "+s+" to "+v+" has no way to access.");
            return;
        }
        while(it.hasNext())
            System.out.print(it.next() + "    ");
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        File f=new File("D:\\arg-data\\tinyG.txt");
        FileInputStream fis=new FileInputStream(f);
        Graph graph=new Graph(fis);
        DepthFirstPaths paths=new DepthFirstPaths(graph,0);
        paths.printEdgeToS();

        System.out.println("-----------");
        paths.printPathToV(6);
    }
}
